#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    bool row[9][10], col[9][10], gride[3][3][10];
    int number = 0;
    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (board[i][j] != '.')
                    row[i][board[i][j] - '0'] = col[j][board[i][j] - '0'] = gride[i / 3][j / 3][board[i][j] - '0'] = true, number++;
        dfs(board, 0, 0);
    }
    void dfs(vector<vector<char>>& board, int x, int y)
    {
        if (number == 81) return;
        if (board[x][y] != '.')
        {
            if (y + 1 == 9) dfs(board, x + 1, (y + 1) % 9);
            else dfs(board, x, (y + 1) % 9);
        }
        else
        {
            for (int i = 1; i <= 9; i++)
            {
                if (row[x][i] || col[y][i] || gride[x / 3][y / 3][i]) continue;
                row[x][i] = col[y][i] = gride[x / 3][y / 3][i] = true;
                board[x][y] = i + '0';
                number++;
                if (y + 1 == 9) dfs(board, x + 1, (y + 1) % 9);
                else dfs(board, x, (y + 1) % 9);
                if (number == 81) return;
                row[x][i] = col[y][i] = gride[x / 3][y / 3][i] = false;
                board[x][y] = '.';
                number--;
            }
        }
    }
};